package demo1;
import java.util.*;

public class DynamicPlanningPractise {
    /**
     * 最后一块石头的重量Ⅱ
     * 时间复杂度O（n*n）
     * 空间复杂度O（n*n）*/
    public int lastStoneWeightIIOther(int[] stones) {
        int sum = 0;
        int n = stones.length;
        for(int x:stones) {
            sum+=x;
        }
        // 不用考虑是不是奇数
        int target = sum/2;
        //1 创建dp表 - 虚拟位置法，多创建一行一列
        int[][] dp = new int[n+1][target+1];
        //2 初始化 - 无需初始化
        //3 填表
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= target; j++) {
                dp[i][j] = dp[i-1][j];
                if(j>=stones[i-1]) {
                    dp[i][j] = Math.max(dp[i][j],dp[i-1][j-stones[i-1]]+stones[i-1]);
                }
            }
        //4 返回值
        return sum-dp[n][target]-dp[n][target];
    }

    /**
     * 同理，我们可以使用滚动数组的方式进行优化
     * 时间复杂度O（n*n）
     * 空间复杂度O（n）*/
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        int n = stones.length;
        for(int x:stones) {
            sum+=x;
        }
        // 不用考虑是不是奇数
        int target = sum/2;
        //1 创建dp表 - 虚拟位置法，多创建一行一列
        int[] dp = new int[target+1];
        //2 初始化 - 无需初始化
        //3 填表
        for(int i = 1; i <= n; i++)
            for(int j = target; j>=stones[i-1]; j--)
                    dp[j] = Math.max(dp[j],dp[j-stones[i-1]]+stones[i-1]);
        //4 返回值
        return sum-dp[target]-dp[target];
    }


}
/**
 * 完全背包问题第一问*/
class Solution {
    /**
     * @param v int整型
     * @param n int整型
     * @param nums int整型ArrayList<ArrayList<>>
     * @return int整型ArrayList
     */
    public ArrayList<Integer> knapsack (int v, int n, ArrayList<ArrayList<Integer>> nums) {
        //0下标为体积 1下标为价值
        //n是元素个数 v是背包总体积

        //1 创建dp表 - 使用虚拟位置法多创建一行一列
        int[][] dp = new int[n+1][v+1];
        //2 初始化 - 无需初始化
        //3 填表
        ArrayList<Integer> ret = new ArrayList<>();
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j <= v; j++) {
                dp[i][j] = dp[i-1][j];
                if(j>=nums.get(i-1).get(0)) {
                    dp[i][j] = Math.max(dp[i][j],dp[i][j-nums.get(i-1).get(0)]+nums.get(i-1).get(1));
                }
            }
        }
        ret.add(dp[n][v]);
        ret.add(0);
        return ret;
    }

    /**
     * 完全背包
     * 已对（1）（2）问进行解答 并对语法进行优化*/
    public ArrayList<Integer> knapsack1 (int v, int n, ArrayList<ArrayList<Integer>> nums) {
        //0下标为体积 1下标为价值
        //n是元素个数 v是背包总体积

        //1 创建dp表 - 使用虚拟位置法多创建一行一列
        int[][] dp = new int[n+1][v+1];
        int[][] dpp = new int[n+1][v+1];
        //2 初始化 - (1)无需初始化 (2)需要对第一行进行初始化
        for(int k = 1; k <= v; k++)
            dpp[0][k] = -1;
        //3 填表
        ArrayList<Integer> ret = new ArrayList<>();
        int max = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j <= v; j++) {
                int tmpV = nums.get(i-1).get(0);//体积
                int tmpW = nums.get(i-1).get(1);//价值
                dp[i][j] = dp[i-1][j];
                dpp[i][j] = dpp[i-1][j];
                if(j>=tmpV) {
                    dp[i][j] = Math.max(dp[i][j],dp[i][j-tmpV]+tmpW);
                    if(dpp[i][j-tmpV]!=-1)
                        dpp[i][j] = Math.max(dpp[i][j],dpp[i][j-tmpV]+tmpW);
                }
                if(j==v) max = Math.max(max,dpp[i][j]);
            }
        }
        //4 返回值
        ret.add(dp[n][v]);
        ret.add(max);
        return ret;
    }

    /**
     * 完全背包
     * 对语法和空间复杂度进行优化
     * 时间复杂度O（n*n）
     * 空间复杂度O（n）*/
    public ArrayList<Integer> knapsack2 (int v, int n, ArrayList<ArrayList<Integer>> nums) {
        //0下标为体积 1下标为价值
        //n是元素个数 v是背包总体积

        //1 创建dp表 - 使用虚拟位置法多创建一行一列
        int[] dp = new int[v+1];
        int[] dpp = new int[v+1];
        //2 初始化 - (1)无需初始化 (2)需要对第一行进行初始化
        for(int k = 1; k <= v; k++)
            dpp[k] = -1;
        //3 填表
        ArrayList<Integer> ret = new ArrayList<>();
        int max = 0;
        for(int i = 1; i <= n; i++) {
            int tmpV = nums.get(i-1).get(0);//体积
            int tmpW = nums.get(i-1).get(1);//价值
            //由于我们在填表时依赖于上方与左方的元素，故每一行的填表顺序一定要是从左到右！
            for(int j = tmpV; j <= v; j++) {
                dp[j] = Math.max(dp[j],dp[j-tmpV]+tmpW);
                if(dpp[j-tmpV]!=-1)
                    dpp[j] = Math.max(dpp[j],dpp[j-tmpV]+tmpW);
                if(j==v) max = Math.max(max,dpp[j]);
            }
        }
        //4 返回值
        ret.add(dp[v]);
        ret.add(max);
        return ret;
    }

    /**
     * 零钱兑换
     * 未进行优化*/
    public int coinChange1(int[] coins, int amount) {
        /**
         思路：个数==价值 面额==体积 总金额==背包容量
         状态表示：
         dp[i][j]表示在前i个硬币中挑选，使得总金额等于j时，最少硬币个数
         状态转移方程：
         根据最后一个元素的状态进行划分问题
         1，不选择coins[i],dp[i][j] = dp[i-1][j]
         2，选择coins[i],dp[i][j] = dp[i][j-coins[i]]+1 -->需满足dp[i][j-coins[i]]不等于-1
         && j >= coins[i]
         取上述两种情况的最小值
         初始化：
         使用虚拟位置法进行初始化
         将第一行1下标之后的状态初始化为-1
         注意下标映射关系
         填表顺序：
         从上到下，从左到右
         */
        int n = coins.length;
        //1 创建dp表
        int[][] dp = new int[n+1][amount+1];
        //2 初始化
        for(int k = 1; k <= amount; k++)
            dp[0][k] = -1;
        //3 填表
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= amount; j++) {
                dp[i][j] = dp[i-1][j];
                if(j>=coins[i-1] && dp[i][j-coins[i-1]]!=-1)
                    //问题出在这里面了，如果dp[i-1][j]为-1，那么最小值必定是它
                    if(dp[i][j]==-1)
                        dp[i][j] = dp[i][j-coins[i-1]]+1;
                    else
                        dp[i][j] = Math.min(dp[i][j-coins[i-1]]+1,dp[i][j]);
            }
        //4 返回值
        return dp[n][amount];
    }

    /**
     * 零钱兑换
     * 使用滚动数组进行优化
     * 时间复杂度O（n*n）
     * 空间复杂度O（n）*/
    public int coinChange(int[] coins, int amount) {
        /**
         思路：个数==价值 面额==体积 总金额==背包容量
         状态表示：
         dp[i][j]表示在前i个硬币中挑选，使得总金额等于j时，最少硬币个数
         状态转移方程：
         根据最后一个元素的状态进行划分问题
         1，不选择coins[i],dp[i][j] = dp[i-1][j]
         2，选择coins[i],dp[i][j] = dp[i][j-coins[i]]+1 -->需满足dp[i][j-coins[i]]不等于-1
         && j >= coins[i]
         取上述两种情况的最小值
         初始化：
         使用虚拟位置法进行初始化
         将第一行1下标之后的状态初始化为-1
         注意下标映射关系
         填表顺序：
         从上到下，从左到右
         */
        int n = coins.length;
        //1 创建dp表
        int[] dp = new int[amount+1];
        //2 初始化
        for(int k = 1; k <= amount; k++)
            dp[k] = -1;
        //3 填表
        for(int i = 1; i <= n; i++)
            for(int j = coins[i-1]; j <= amount; j++) {
                if(dp[j-coins[i-1]]!=-1)
                    if(dp[j]==-1)
                        dp[j] = dp[j-coins[i-1]]+1;
                    else
                        dp[j] = Math.min(dp[j-coins[i-1]]+1,dp[j]);
            }
        //4 返回值
        return dp[amount];
    }
    /**
     * 最后一块石头的重量Ⅱ - 修改
     * 时间复杂度O（n*n）
     * 空间复杂度O（n*n）*/
    public int lastStoneWeightIIOther(int[] stones) {
        int sum = 0;
        int n = stones.length;
        for(int x:stones) {
            sum+=x;
        }
        // 不用考虑是不是奇数
        int target = sum/2;
        //1 创建dp表 - 虚拟位置法，多创建一行一列
        int[][] dp = new int[n+1][target+1];
        //2 初始化 - 无需初始化
        //3 填表
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= target; j++) {
                dp[i][j] = dp[i-1][j];
                if(j>=stones[i-1]) {
                    dp[i][j] = Math.max(dp[i][j],dp[i-1][j-stones[i-1]]+stones[i-1]);
                }
            }
        //4 返回值
        return sum-dp[n][target]-dp[n][target];
    }
}